public class BinarySearchTree {

    //用静态内部类来定义二叉树的结点
    static class TreeNode {
        int key;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int key) {
            this.key = key;
        }
    }

    //定义二叉搜索树的根节点
    public TreeNode root;

    //二叉搜索树的查找
    //递归写法

    /**
     *
     * @param key 需要插入的值
     * @param root 想要插入的二叉搜索树的根节点
     * @return  查找的结果
     */
    public boolean search(int key,BinarySearchTree.TreeNode root) {
        //二叉搜索树为空
       if(this.root == null) {
           return false;
       }


       TreeNode cur = root;
       if(cur.key == key) {
           return true;
       } else if (cur.key > key) {
           search(key,root.leftChild);
       } else {
           search(key,root.rightChild);
       }

       return false;

    }

    //二叉排序树的查找
    //非递归写法
    public boolean search(int key) {
        //判空
        if(this.root == null) {
            return false;
        }

        TreeNode cur = this.root;

        while(cur != null ) {
             if(cur.key < key) {
                 //在左子树中查找
                 cur = cur.rightChild;
             } else if (cur.key > key) {
                 //在右子树中查找
                 cur = cur.leftChild;
             } else {
                 //找到了
                 return true;
             }
        }

        //如果代码走到这里，还是没有找到，说明二叉搜索树中没有该元素
        return false;
    }

    //二叉搜索树的插入
    /**
     *
     * @param key 想要插入的值
     *
     */
    public void insert(int key) {
        TreeNode newNode = new TreeNode(key);

        //处理根节点为空的情况
         if(this.root == null) {
             this.root = newNode;
             return;
         }
         TreeNode cur = root;
         TreeNode parent = null;

         //寻找插入的位置
        //用parent来记录cur的双亲结点
        while(cur != null) {
            if(cur.key == key) {
                return;
            } else if (cur.key < key) {
                parent = cur;
                cur = cur.rightChild;
            } else {
                parent = cur;
                cur = cur.leftChild;
            }
        }

        //代码走到这里，cur == null parent指向要插入的位置
        //只需判断key和parent.key的大小进行插入即可
        if(parent.key > key) {
            parent.leftChild = newNode;
        }else {
            parent.rightChild = newNode;
        }
    }

    //二叉排序树的删除
    //寻找待删除的结点
    public void remove(int key) {

        TreeNode curNode = this.root;
        TreeNode curParent = null;

        while(curNode != null) {
             //如果当前结点的值
            if(curNode.key > key) {
                curParent = curNode;
                curNode = curNode.leftChild;
            } else if (curNode.key < key) {
                curParent = curNode;
                curNode = curNode.rightChild;
            } else {
                //开始删除结点
                removeNode(curNode,curParent);
                return;
            }
        }
    }

    //删除结点
    /**
     * @param cur 待删除的结点
     * @param parent 待删除结点的双亲结点
     */
    public void removeNode(TreeNode cur,TreeNode parent) {
        if(cur.rightChild == null) {
            if(cur == root) {
                root = cur.leftChild;
            } else if (parent.leftChild == cur) {
                parent.leftChild = cur.leftChild;
            } else {
                parent.rightChild = cur.leftChild;
            }
        } else if (cur.leftChild == null) {
            if(cur == root) {
                root = cur.rightChild;
            } else if (cur == parent.leftChild) {
                parent.leftChild = cur.rightChild;
            } else {
                parent.rightChild = cur.rightChild;
            }
        } else {
            //寻找右子树中的最小结点
            TreeNode tmp = cur.rightChild;
            TreeNode tmpParent = cur;

            while(tmp.leftChild != null) {
                tmpParent = tmp;
                tmp = tmp.leftChild;
            }

            //代码走到这里，Tmparent指向待替换的结点的双亲
            cur.key = tmp.key;

            //判断tmp和tmpParent的相对位置
            if(tmpParent.leftChild == tmp) {
                tmpParent.leftChild = tmp.rightChild;
            } else {
                tmpParent.rightChild = tmp.rightChild;
            }
        }

    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] array = new int[]{5,10,3,1,15};
        for (int i = 0; i < array.length; i++) {
            bst.insert(array[i]);
        }
        bst.remove(5);
    }
}
